package seach

func BucketSort(li []int, n int, maxNum int) []int {
	if maxNum == 0 {
		maxNum = 1000000
	}
	if n == 0 {
		n = 10000
	}
	buckets := make([][]int, n)
	for _, val := range li {
		i := val / (maxNum / n)
		if i >= n {
			i = n - 1
		}
		//将数字放入桶中并排序
		buckets[i] = append(buckets[i], val)
		for bi := len(buckets[i]) - 1; len(buckets[i]) > 1 && bi > 0; bi-- {
			if buckets[i][bi] < buckets[i][bi-1] {
				buckets[i][bi], buckets[i][bi-1] = buckets[i][bi-1], buckets[i][bi]
			} else {
				break
			}
		}
	}
	sortedLi := make([]int, 0, len(li))
	for _, bucket := range buckets {
		sortedLi=append(sortedLi,bucket...)
	}
	return sortedLi
}
